package hot100;

public class LengthOfLIS {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];//dp[i]为以nums[i]为结尾的子序列的最大长度
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        //遍历每个位置
        int res = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                    res = Math.max(res,dp[i]);
                }
            }
        }
        return res;
    }
}
